#include <stdio.h>
#include <stdlib.h>

#define MAX_TREE_SIZE 100

typedef int TElemType;  // 树节点的数据类型
typedef struct PTNode{
  TElemType data;
  int parent;
}PTNode;
typedef struct{
  PTNode nodes[MAX_TREE_SIZE];
  int r, n;
}PTree;

typedef struct CTNode{
  int child;
  struct CTNode *next;
}*ChildPtr;
typedef struct{
  TElemType data;
  ChildPtr firstchild;
}CTBox;
typedef struct{
  CTBox nodes[MAX_TREE_SIZE];
  int r, n;
}CTree;

typedef struct CSNode{
  TElemType data;
  struct CSNode *firstchild, *rightsib;
} CSNode, *CSTree;

/*============================BitTree====================================================*/
typedef struct BitNode{
  TElemType data;
  struct BitNode *lchild, *rchild;
}BitNode, *BitTree;

void freeBitTree(BitTree tree)
{
  if (tree != NULL) {
    freeBitTree(tree->lchild);
    tree->lchild = nullptr;
    freeBitTree(tree->rchild);
    tree->rchild = nullptr;
    free(tree);
  }
}

void visit(BitTree tree)
{
  if (tree != NULL) {
    printf("%d ", tree->data);
  }
}

void preOrder(BitTree tree)
{
  if (tree != NULL) {
    visit(tree);
    preOrder(tree->lchild);
    preOrder(tree->rchild);
  }
}

void inOrder(BitTree tree)
{
  if (tree != NULL) {
    inOrder(tree->lchild);
    visit(tree);
    inOrder(tree->rchild);
  }
}

void postOrder(BitTree tree)
{
  if (tree != NULL) {
    postOrder(tree->lchild);
    postOrder(tree->rchild);
    visit(tree);
  }
}

BitTree createBitTree()
{
  int data = 0;
  scanf("%d", &data);
  if (data <= 0) {
    return NULL;
  }

  BitTree tree = (BitTree)malloc(sizeof(BitNode));
  if (tree == NULL) {
    return NULL;
  }
  tree->data = data;
  tree->lchild = createBitTree();
  tree->rchild = createBitTree();

  return tree;
}

int main()
{
  BitTree tree = createBitTree();
  if (tree == NULL) {
    return -1;
  }

  preOrder(tree); printf("\n");
  inOrder(tree); printf("\n");
  postOrder(tree); printf("\n");

  freeBitTree(tree);
  return 0;
}

